Mathematical Formulation of Linear Programming Problems

General Structure of a Linear Programming Problem

Core Components of an LPP

Every Linear Programming Problem (LPP) is built upon a foundation of distinct, interconnected components. Understanding these components is the first crucial step in formulating any LPP from a real-world scenario. A standard LPP is defined by the following four main parts:

1. Decision Variables: These are the fundamental unknowns in the problem. They represent the controllable quantities or choices that need to be made by the decision-maker. The ultimate goal of solving the LPP is to find the optimal values for these variables. They are typically denoted by symbols like $x_1, x_2, \dots, x_n$, where $n$ is the number of variables. The values assigned to these variables directly influence the outcome (objective function value) and whether the constraints are met.

2. Objective Function: This is a linear mathematical expression that represents the overall aim or goal of the problem. It is the quantity that is to be optimized, meaning we either want to find its maximum possible value (e.g., maximum profit, revenue, output) or its minimum possible value (e.g., minimum cost, time, waste). The objective function is always expressed as a linear combination of the decision variables and is commonly denoted by $Z$.

   For instance, if $x_1, x_2, \dots, x_n$ are the decision variables and $c_1, c_2, \dots, c_n$ are their respective per-unit contributions to the objective (like profit per unit), the objective function would look like:

   Optimize $Z = c_1 x_1 + c_2 x_2 + \dots + c_n x_n$

3. Constraints: These are a set of linear inequalities or, occasionally, linear equations that represent the limitations or restrictions on the decision variables. Constraints model the real-world boundaries within which the problem exists, such as limited availability of resources (like raw materials, labour, machine capacity), budget restrictions, minimum production requirements, demand limits, or technical specifications. They define the set of all feasible solutions.

   Each constraint $i$ (out of $m$ total constraints) will typically be in the form:

   $a_{i1} x_1 + a_{i2} x_2 + \dots + a_{in} x_n \mathrel{\{\leq, \geq, =\}} b_i$

   [Form of Constraint i]

   Here, $a_{ij}$ are coefficients representing the resource usage or requirement per unit of $x_j$ in constraint $i$, and $b_i$ is the total availability or requirement for constraint $i$. All feasible values of the decision variables must satisfy every single constraint simultaneously.

4. Non-negativity Restrictions: These are a special but standard type of constraint present in almost all practical LPPs. They stipulate that the decision variables cannot take negative values; they must be greater than or equal to zero.

   For the decision variables $x_1, x_2, \dots, x_n$, these restrictions are:

   $x_1 \ge 0, x_2 \ge 0, \dots, x_n \ge 0$

   These constraints are crucial because, in most real-world applications, decision variables represent physical quantities (like the number of items, amount of material, time) that cannot be negative.

The process of carefully reading a real-world problem description, identifying these four components, and translating them into a concise mathematical representation is called the mathematical formulation of the Linear Programming Problem. A correct formulation is the prerequisite for solving the LPP.

Illustrative Example of LPP Structure Identification

Answer:

Recognizing and correctly defining these four structural elements is the foundational skill needed to tackle any problem using Linear Programming.

Mathematical Formulation of Linear Programming Problem (Consolidated)

The Complete LPP Model

The mathematical formulation of a Linear Programming Problem is the process of translating the verbal description of a real-world problem into a structured set of mathematical expressions. Once the four core components (decision variables, objective function, constraints, and non-negativity restrictions) have been identified, they are written together in a standard, consolidated format. This format clearly presents the problem in a way that is ready for solution by appropriate algorithms (like the Graphical Method or Simplex Method).

For a general LPP with $n$ decision variables ($x_1, x_2, \dots, x_n$) and $m$ functional constraints, the consolidated mathematical formulation is presented as follows:

General Mathematical Form:

Determine the values of the variables $x_1, x_2, \dots, x_n$

in order to Optimize (either Maximize or Minimize) the objective function $Z$:

This is often written concisely using summation notation:

Subject to the constraints:

The $m$ functional constraints are typically listed individually. Each constraint $i$ ($i=1, 2, \dots, m$) takes the form:

...

Alternatively, the set of $m$ constraints can be expressed concisely using summation notation for each constraint:

And subject to the non-negativity restrictions:

All decision variables must be non-negative.

Understanding the Notation

The symbols used in the general formulation have specific meanings:

• $x_j$: Represents the $j$-th decision variable (where $j$ goes from 1 to $n$). These are the quantities to be determined.
• $Z$: Represents the value of the objective function that is being optimized.
• $c_j$: Represents the coefficient of the $j$-th decision variable $x_j$ in the objective function. $c_j$ indicates the per-unit contribution of $x_j$ to the objective value $Z$.
• $a_{ij}$: Represents the coefficient of the $j$-th decision variable $x_j$ in the $i$-th constraint. $a_{ij}$ quantifies the amount of resource $i$ consumed or contribution made to requirement $i$ by one unit of $x_j$.
• $b_i$: Represents the right-hand side (RHS) value of the $i$-th constraint. $b_i$ denotes the total available amount of resource $i$ (for $\leq$), the minimum required amount for condition $i$ (for $\geq$), or the exact value for condition $i$ (for $=$).
• $n$: The total number of decision variables.
• $m$: The total number of functional constraints (excluding the $n$ non-negativity constraints).
• $\sum_{j=1}^{n}$: This is summation notation, meaning "sum from $j=1$ to $n$". It's a compact way to write sums involving multiple variables. For example, $\sum_{j=1}^{3} c_j x_j$ means $c_1 x_1 + c_2 x_2 + c_3 x_3$.

This consolidated form provides a complete and precise mathematical representation of the LPP, which is essential for applying standard solution techniques.

Example of Consolidated Formulation

Answer:

The consolidated mathematical formulation is the standard way to present a Linear Programming Problem, clearly outlining the objective and the limitations that define the problem space.

Formation of an L.P.P in Two Variables (x and y)

Step-by-Step Formulation for Two Variables

Many introductory problems in Linear Programming, especially those solved using the graphical method, involve only two decision variables. While the general formulation applies to any number of variables, let's focus on the systematic process for formulating LPPs with exactly two variables, conventionally denoted as $x$ and $y$. This process involves translating the problem description from words into mathematical expressions.

Here are the key steps involved in forming a Linear Programming Problem with two variables:

1. Step 1: Identify and Define the Decision Variables.

   Carefully read the problem statement to determine the quantities that are unknown and whose values need to be decided to achieve the objective. Assign variables, commonly $x$ and $y$, to these quantities. Clearly and precisely define what each variable represents, including the units if applicable (e.g., "Let $x$ be the number of units of Product P produced," "Let $y$ be the kilograms of ingredient Q used"). These variables represent the choices or decisions to be made.

2. Step 2: Identify and Formulate the Objective Function.

   Determine the goal of the problem. Is it to maximize a quantity (like profit, revenue, yield) or minimize a quantity (like cost, time, distance)? Identify how the decision variables $x$ and $y$ contribute to this goal. Write this goal as a linear mathematical expression involving $x$ and $y$. This expression is the objective function, typically denoted as $Z$. The form will be $Z = c_1 x + c_2 y$, where $c_1$ and $c_2$ are the per-unit contributions of $x$ and $y$ to the objective. State clearly whether the objective is to Maximize $Z$ or Minimize $Z$.

3. Step 3: Identify and Formulate the Constraints.

   Go through the problem statement again to identify all the limitations, restrictions, or requirements that the decision variables must satisfy. These usually relate to limited resources or minimum requirements. For each such condition, translate the verbal description into a linear inequality or equation involving $x$ and $y$. Ensure consistency in units across the constraint.

   For example, a resource constraint might be $a_1 x + b_1 y \leq R_1$ (total resource used $\leq$ total resource available), or a minimum requirement might be $a_2 x + b_2 y \geq M_2$ (total quantity obtained $\geq$ minimum required quantity).

4. Step 4: Add the Non-negativity Restrictions.

   In most practical problems, the decision variables represent physical quantities that cannot be negative. Therefore, it is essential to include the non-negativity constraints, which state that the decision variables must be greater than or equal to zero: $x \ge 0$ and $y \ge 0$.

5. Step 5: Consolidate the LPP.

   Gather all the formulated parts and write down the complete Linear Programming Problem in the standard format:

   • Start with the objective (Maximize Z or Minimize Z).
   • Follow with "Subject to the constraints:".
   • List all the functional constraints formulated in Step 3.
   • Finally, list the non-negativity restrictions from Step 4.

   This consolidated formulation provides a clear and organized mathematical model of the problem.

Following these steps systematically helps in accurately translating a word problem into a solvable LPP.

Example of Forming an LPP in Two Variables

Answer:

This systematic approach ensures that all conditions and the objective of the problem are accurately represented in the mathematical model, making it ready for solution. Problems with more than two variables follow the same logical steps but result in models that typically require computational methods (like the Simplex algorithm) rather than the graphical method for solution.

Translating Real-World Problems into Mathematical Formulation

The Process of Formulation

The most critical step in using Linear Programming to solve a real-world problem is accurately translating the problem's description from natural language into a precise mathematical model. This process, known as mathematical formulation, involves identifying the core components of the problem and representing them using linear equations and inequalities. A correctly formulated LPP is essential, as any error in the model will lead to an incorrect solution.

Here is a systematic approach to guide you through the process of translating a verbal problem description into a standard Linear Programming Problem formulation:

1. Step 1: Thoroughly Understand the Problem.

   Read the problem statement multiple times to fully grasp the scenario, the context, and the underlying relationships. Identify the key elements:

   • What is the ultimate goal? Is it to achieve the best possible outcome (maximize something) or minimize expenditure or effort (minimize something)? This will define the objective function.
   • What are the decisions that need to be made to achieve this goal? What quantities can be varied or controlled? These are your decision variables.
   • What are the restrictions, limitations, or requirements that must be respected? These represent the constraints (e.g., limited resources, minimum quality standards, demand limits).

   Extract all relevant numerical data associated with profits, costs, resource consumption rates, resource availabilities, and requirements.

2. Step 2: Define the Decision Variables.

   Based on the decisions identified in Step 1, assign clear algebraic symbols (like $x, y$, or $x_1, x_2, \dots, x_n$) to represent the unknown quantities. It is vital to provide a precise definition for each variable, including the units of measurement. For example, instead of just "let $x$ be product A", define it as "Let $x$ be the number of units of Product A produced per day/week/month" or "Let $x$ be the kilograms of ingredient A to be used". This clarity prevents confusion during formulation and interpretation of the solution.

3. Step 3: Formulate the Objective Function.

   Write a linear mathematical expression that represents the overall goal identified in Step 1, in terms of the decision variables defined in Step 2. Determine how each unit of a decision variable contributes to the objective (e.g., profit per unit, cost per unit). Use these contributions as the coefficients for the respective variables in the objective function. Denote the objective function by $Z$. Clearly state whether the objective is to Maximize $Z$ or Minimize $Z$. Remember, the objective function must be linear.

4. Step 4: Formulate the Constraints.

   Translate each limitation, restriction, or requirement identified in Step 1 into a linear inequality or equation involving the decision variables.

   • Pay close attention to keywords like:
     • "at most", "no more than", "maximum capacity of", "limited to" (implies $\leq$).
     • "at least", "no less than", "minimum requirement of" (implies $\geq$).
     • "exactly", "equal to", "is" (implies $=$).
   • For each constraint, determine the coefficients ($a_{ij}$) representing the amount of resource consumed or requirement contributed per unit of each decision variable ($x_j$). The left side of the constraint will be a linear combination of the variables ($\sum a_{ij} x_j$).
   • Determine the right-hand side ($b_i$) value, which is the total amount of the resource available or the required level.
   • Ensure that units are consistent on both sides of every constraint equation or inequality. If the left side represents total hours, the right side must also be in hours.

   List all these functional constraints clearly.

5. Step 5: Add the Non-negativity Restrictions.

   For almost all real-world LPPs, the decision variables represent physical or countable quantities that cannot be negative. Therefore, explicitly state that all decision variables must be greater than or equal to zero ($x \ge 0, y \ge 0, x_j \ge 0$ for all $j$). While seemingly obvious, these are critical for defining the feasible region correctly.

6. Step 6: Consolidate and Review the Formulation.

   Write the complete LPP model in a standard format:

   • State the optimization objective (Maximize Z or Minimize Z) and the objective function.
   • Write "Subject to the constraints:".
   • List all the functional constraints formulated in Step 4.
   • List the non-negativity restrictions from Step 5.

   Finally, review the complete mathematical formulation against the original problem statement. Does the model accurately capture all the essential information and relationships? Are all coefficients and RHS values correct? Is it truly linear? This review helps catch errors before attempting to solve the problem.

Example Translation: A Diet Problem

Answer:

Mastering the skill of translating real-world problems into mathematical LPP models is fundamental to applying Linear Programming techniques effectively. It requires careful reading, clear definition of variables, and accurate representation of the objective and all constraints as linear expressions.